package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.ListNode;

/*
 * 
原题　
		61.Rotate List
	
	Given a list, rotate the list to the right by k places, where k is non-negative.
	
	For example:
	Given 1->2->3->4->5->NULL and k = 2,
	return 4->5->1->2->3->NULL.
题目大意
	　
解题思路
	@TODO:
 * @Date 2017-09-14 23：43
 */
public class _061_Rotate_List {
    public ListNode rotateRight(ListNode head, int k) {
    	int size = getListLength(head);
    	//全链表反转
    	ListNode head1 = reverseList(head, size);
    	ListNode.traverse("reverse结果--------head1", head1);
    	ListNode head2 = reverseList(head1, k);					//反转前2位
    	
    	ListNode.traverse("find结果--------", find(head1, 1));
    	find(head2, k-1).next = reverseList(find(head2, k), size-k);
    	ListNode.traverse("reverse结果--------", head2);
        return null;
    }
    

    
    /**
     * 找到第num个节点
     * @param index
     * @return
     */
    public ListNode find(ListNode head, int num) {
    	int count = 0;
    	ListNode p = head;
    	while (p!=null && count<num) {
    		count++;
    		p = p.next;
    	}
    	return p;
    }
    
    /**
     * 得到链表总长度
     * @param head
     * @return
     */
    public int getListLength(ListNode head) {
    	int total = 0;
    	ListNode p = head;
    	while (p != null) {
    		total++;
    		p = p.next;
    	}
    	return total;
    }
    
    /**
     * 反转单链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head, int n) {
    	if (head == null)	return null;
    	ListNode p = head, q = p.next;
    	ListNode temp = q;
    	p.next = null;
 
    	int count = 0;
    	while (q!=null && count<n-1) {
    		count++;
    		temp = q.next;
    		q.next = p;
    		p = q;
    		q = temp;
    	}
    	ListNode.traverse("reverse结果"+n, p);
     	return p;
    }
    
    
	public static ListNode newLinkListOrdered() {
		ListNode root = new ListNode(1);
		root.next = new ListNode(2);
		root.next.next = new ListNode(3);
		root.next.next.next = new ListNode(4);
		root.next.next.next.next = new ListNode(5);
		return root;
	}
	
    
	public static void main(String[] args) {
		_061_Rotate_List obj = new _061_Rotate_List();
		obj.rotateRight(newLinkListOrdered(), 2);
	}

}
